package com.zbl.小题大做;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/*
- 有序排列
- 每次插入都会排序，调整量不大
 */
public class 堆 {
    // 在一条线上取不同的线段，找最多重叠的线段次数
    public static int maxCover(int [][] arr) {
        Arrays.sort(arr, (a, b) -> (a[0] - b[0]));

        int ans = 0;
        PriorityQueue<Integer> head = new PriorityQueue<>();
        for (int[] line : arr) {
            while(!head.isEmpty() && head.peek() <= line[0]) {
                head.poll();
            }
            head.add(line[1]);
            ans = Math.max(ans, head.size());
        }

        return ans;
    }

    // 分金块，金块多次分割，完成预定大小。每次被分割的金块大小计为成本，求最小成本
    public static int minCost(Integer [] arr) {
        PriorityQueue<Integer> head = new PriorityQueue<>(Arrays.asList(arr));

        int ans = 0;
        int mix = 0;
        while (head.size() > 1) {
            Integer L = head.poll();
            Integer R = head.poll();
            mix = L + R;
            ans += mix;
            head.add(mix);
        }

        return ans;
    }
    public static void main(String[] args) {
        //1\System.out.println(maxCover(new int[][]{{1, 2}, {2, 4}, {3, 5}, {4, 5}}));
        Integer[] integers = new Integer[5];
        integers[0] = 1;
        integers[1] = 2;
        integers[2] = 3;
        integers[4] = 4;
        integers[3] = 5;
        System.out.println(minCost(integers));
    }

}
